namespace bucketHash {

	template<class T>
	struct HashNode {
		T _data;
		HashNode<T>* _next;
		HashNode(const T& data)
			:_next(nullptr)
			,_data(data)  
		{}
	};

	template<class K, class T, class Hash, class KeyOfT>
	class HashBucket;
	template<class K, class T, class Hash, class KeyOfT>
	struct __HTIterator {
		typedef HashNode<T> Node;
		typedef __HTIterator<K, T, Hash, KeyOfT> Self;
		typedef HashBucket<K, T, Hash, KeyOfT> HT;
		HT* _ht;
		Node* _node;
		__HTIterator(Node* node,HT* ht)
			:_node(node)
			,_ht(ht)
		{}
		T& operator*()
		{
			return _node->_data;
		}
		bool operator!=(const Self& s) const
		{
			return s._node != _node;
		}
		T* operator->()
		{
			return &_node->_data;
		}
		Self& operator++()
		{
			if (_node->_next)
			{
				_node = _node->_next;
			}
			else
			{
				KeyOfT kot;
				size_t hashi = Hash()(kot(_node->_data)) % _ht->_table.size();
				//从下一个位置开始寻找
				++hashi;
				while (hashi < _ht->_table.size())
				{
					if (_ht->_table[hashi])
					{
						_node = _ht->_table[hashi];
						break;
					}
					else
					{
						++hashi;
					}
				}
				//后面没有桶
				if (hashi == _ht->_table.size())
					_node = nullptr;
			}
			return *this;
		}
	};

	//这里的Hash function应该由上层传入，即unorderedmap和unorderedset 还需要传入KeyOfT
	template<class K,class T,class Hash,class KeyOfT>
	class HashBucket {
		typedef HashNode<T> Node;
		template<class K, class T, class Hash, class KeyOfT>
		friend struct __HTIterator;
	public:
		typedef __HTIterator<K, T, Hash, KeyOfT> iterator;

		iterator begin()
		{
			for (size_t i = 0; i < _table.size(); ++i)
			{
				if (_table[i])
				{
					return iterator(_table[i],this);
				}
			}
			return iterator(nullptr,this);
		}
		iterator end()
		{
			return iterator(nullptr,this);
		}

	public:
		HashBucket()
			:_n(0)
		{
			_table.resize(10, nullptr);
		}
		//需要调用析构函数
		//内置类型不做处理，自定义类型调用自己的析构函数
		//
		~HashBucket()
		{
			for (size_t i = 0; i < _table.size(); ++i)
			{
				Node* cur = _table[i];
				Node* next = nullptr;
				while (cur)
				{
					next = cur->_next;
					delete cur;
					cur = next;
				}
			}
			_table.resize(0);
		}
		pair<iterator,bool> insert(const T& data)
		{
			iterator it = Find(KeyOfT()(data));
			if (it !=end())
				return make_pair(it,false);
			//扩容，当负载因子为1的时候
			if (_n == _table.size())
			{
				//这时候为了节省new节点的空间，选择重复利用挂在旧表上的节点
				//直接new 一个新的table出来即可
				vector<Node*> NewTable;
				NewTable.resize(_table.size() * 2, nullptr);
				//把旧表的节点链接在新表上
				for (size_t i = 0; i < _table.size(); ++i)
				{
					if (i == 8)
					{
						cout << endl;
					}
					Node* cur = _table[i];
					Node* prev = nullptr;
					while (cur)
					{
						prev = cur->_next;
						int hashi = Hash()(KeyOfT()(cur->_data)) % NewTable.size();
						Node* next = NewTable[hashi];
						cur->_next = next;
						NewTable[hashi] = cur;
						cur = prev;
					}
				}
				//交换新表旧表
				_table.swap(NewTable);
			}

			//跟表一样首先需要计算hashi
			size_t hashi = Hash()(KeyOfT()(data)) % _table.size();
			//选择头插
			Node* newnode = new Node(data);
			newnode->_next = _table[hashi];
			_table[hashi] = newnode;
			_n++;
			return make_pair(iterator(newnode,this),true);

		}
		iterator Find(const K& key)
		{
			size_t hashi = Hash()(key) % _table.size();

			Node* cur = _table[hashi];
			while (cur)
			{
				if (KeyOfT()(cur->_data ) == key)
				{
					return iterator(cur,this);
				}
				else
				{
					cur = cur->_next;
				}
			}
			return end();
		}
		bool Erase(const K& key)
		{
			int hashi = Hash()(key) % _table.size();
			Node* cur = _table[hashi];
			Node* prev = nullptr;
			while (cur)
			{
				if (KeyOfT()(cur->_data) == key)
				{
					//假设第一个就是要查找的对象
					if (_table[hashi]->_kv.first == key)
					{
						prev = cur->_next;
						delete cur;
						_table[hashi] = prev;
					}
					else
					{
						prev->_next = cur->_next;
						delete cur;
						cur = nullptr;
					}
					--_n;
					return true;
				}
				else
				{
					prev = cur;
					cur = cur->_next;
				}
			}
			return false;
		}
	private:
		vector<Node*> _table;    //指针数组
		size_t _n=0 ;
	};
}